#include <cstdio>
#include <iostream>
using namespace std;
#define Mod 1000000007
const int MAXN = 1000000;
int k , prime[ MAXN / 10 + 5 ] , mu[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( int x ) {
mu[ 1 ] = 1;
for( int i = 2 ; i <= x ; i ++ ) {
if( !vis[ i ] ) {
prime[ ++ k ] = i;
mu[ i ] = -1;
}
for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= x ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) break;
mu[ i * prime[ j ] ] = -mu[ i ];
}
}
}
int Quick_pow( int x , int po ) {
int Ans = 1;
while( po ) {
if( po % 2 )
Ans = 1ll * Ans * x % Mod;
x = 1ll * x * x % Mod;
po /= 2;
}
return Ans;
}
int Inv( int x ) {
return Quick_pow( x , Mod - 2 );
}
int t , n , m;
int f[ MAXN + 5 ] = { 0 , 1 , 1 } , finv[ MAXN + 5 ] = { 0 , 1 , 1 } , F[ MAXN + 5 ];
void Init( ) {
sieve( MAXN );
for( int i = 3 ; i <= MAXN ; i ++ ) {
f[ i ] = ( f[ i - 1 ] + f[ i - 2 ] ) % Mod;
finv[ i ] = Inv( f[ i ] );
}
for( int i = 0 ; i <= MAXN ; i ++ )
F[ i ] = 1;
for( int i = 1 ; i <= MAXN ; i ++ ) {
if( !mu[ i ] ) continue;
for( int j = i ; j <= MAXN ; j += i )
F[ j ] = ( 1ll * F[ j ] * ( mu[ i ] == 1 ? f[ j / i ] : finv[ j / i ] ) ) % Mod;
}
for( int i = 2 ; i <= MAXN ; i ++ )
F[ i ] = 1ll * F[ i - 1 ] * F[ i ] % Mod;
}
int solve( int n , int m ) {
int d = n < m ? n : m , Ans = 1;
for( int l = 1 , r ; l <= d ; l = r + 1 ) {
r = min( n / ( n / l ) , m / ( m / l ) );
Ans = 1ll * Ans * Quick_pow( 1ll * F[ r ] * Inv( F[ l - 1 ] ) % Mod , 1ll * ( n / l ) * ( m / l ) % ( Mod - 1 ) ) % Mod;
}
return ( Ans + Mod ) % Mod;
}
int main( ) {
Init( );
scanf("%d",&t);
while( t -- ) {
scanf("%d %d",&n,&m);
printf("%d\n",solve( n , m ));
}
return 0;
}